package   {
	import flash.display.Sprite;

	public class AStar extends Sprite {
		private var _open:Array; //开放列表
		private var _closed:Array; //封闭列表
		private var _grid:Grid;
		private var _endNode:Node; //终点
		private var _startNode:Node; //起点
		private var _path:Array; //最终的路径节点
		// private var _heuristic:Function = manhattan; 
		// private var _heuristic:Function = euclidian; 
		private var _heuristic:Function = diagonal; //估计公式
		private var _straightCost:Number = 1.0; //直线代价        
		private var _diagCost:Number = Math.SQRT2; //对角线代价        

		public function AStar() {

		}

		//判断节点是否开放列表
		private function isOpen(node:Node):Boolean {
			for (var i:int = 0; i < _open.length; i++) {
				if (_open[i] == node) {
					return true;
				}
			}
			return false;
		}

		//判断节点是否封闭列表
		private function isClosed(node:Node):Boolean {
			for (var i:int = 0; i < _closed.length; i++) {
				if (_closed[i] == node) {
					return true;
				}
			}
			return false;
		}

		//对指定的网络寻找路径
		public function findPath(grid:Grid):Boolean {
			_grid = grid;
			_open = new Array();
			_closed = new Array();
			_startNode = _grid.startNode;
			_endNode = _grid.endNode;
			_startNode.g = 0;
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			return search();
		}

		//计算周围节点代价的关键处理函数
		public function search():Boolean {
			var _t:uint = 1;
			var node:Node = _startNode;
			//如果当前节点不是终点
			while (node != _endNode) {
				//找出相邻节点的x,y范围
				var startX:int = Math.max(0, node.x - 1);
				var startY:int = Math.max(0, node.y - 1);
				var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
				var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

				//循环处理所有相邻节点
				for (var i:int = startX; i <= endX; i++) {
					for (var j:int = startY; j <= endY; j++) {
						var test:Node = _grid.getNode(i, j);
						//如果是当前节点，或者是不可通过的，且排除水平和垂直方向都是障碍物节点时的特例情况
						if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable) {
							continue;
						}

						var cost:Number = _straightCost;
						//如果是对象线，则使用对角代价
						if (!((node.x == test.x) || (node.y == test.y))) {
							cost = _diagCost;
						}

						//计算test节点的总代价                      
						var g:Number = node.g + cost * test.costMultiplier;
						var h:Number = _heuristic(test);
						var f:Number = g + h;


						//如果该点在open或close列表中
						if (isOpen(test) || isClosed(test)) {
							//如果本次计算的代价更小，则以本次计算为准
							if (f < test.f) {
								trace("\n第", _t, "轮，有节点重新指向，x=", i, "，y=", j, "，g=", g, "，h=", h, "，f=", f, "，test=", test.toString());
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node; //重新指定该点的父节点为本轮计算中心点
							}
						} else //如果还不在open列表中，则除了更新代价以及设置父节点，还要加入open数组
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.push(test);
						}
					}
				}
				_closed.push(node); //把处理过的本轮中心节点加入close节点               

				//辅助调试，输出open数组中都有哪些节点
				for (i = 0; i < _open.length; i++) {
					trace(_open[i].toString());
				}

				if (_open.length == 0) {
					trace("没找到最佳节点，无路可走!");
					return false
				}
				_open.sortOn("f", Array.NUMERIC); //按总代价从小到大排序
				node = _open.shift() as Node; //从open数组中删除代价最小的结节，同时把该节点赋值为node，做为下次的中心点
				trace("第", _t, "轮取出的最佳节点为：", node.toString());
				_t++;
			}
			//循环结束后，构建路径
			buildPath();
			return true;
		}

		//根据父节点指向，从终点反向连接到起点
		private function buildPath():void {
			_path = new Array();
			var node:Node = _endNode;
			_path.push(node);
			while (node != _startNode) {
				node = node.parent;
				_path.unshift(node);
			}
		}

		//曼哈顿估价法
		private function manhattan(node:Node):Number {
			return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y - _endNode.y) * _straightCost;
		}

		//几何估价法
		private function euclidian(node:Node):Number {
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}

		//对角线估价法
		private function diagonal(node:Node):Number {
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}

		//返回所有被计算过的节点(辅助函数)
		public function get visited():Array {
			return _closed.concat(_open);
		}

		//返回open数组
		public function get openArray():Array {
			return this._open;
		}

		//返回close数组
		public function get closedArray():Array {
			return this._closed;
		}

		public function get path():Array {
			return _path;
		}
	}
}
